

//前言:
//--前两个容器有一个共同点,其底层的实现都是按照搜索二叉树实现的,但是搜索二叉树有自身的缺陷,也就是加入往二叉树中插入有序或者接近有序的元素,二叉树就可能会退化成单链表的形式,时间复杂度就会退化成 O(N)
//因此 map,set 容器的底层是对二叉树进行了平衡处理,也就是采用平衡树实现的

//一个是 avl 树(这个也叫高度平衡搜索二叉树),另一个是红黑树(更抽象,是通过控制颜色来进行控制的)





//一丶 AVL 树的概念
//带着这个问题去学习:avl 树不一定需要平衡因子,使用平衡因子是一种控制的实现方式
//但是有的方式是不用加平衡因子来实现的

//1.搜索二叉树虽然可以缩短查找的效率,但是可能会退化成单支树,查找元素相当于在单链表中进项查找,效率就会非常的低
//--其解决方式就是:当向搜索二叉树插入新的结点以后,如果能保证每个结点的左右子树高度差的绝对值不超过 1(需要在树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度
//平衡因子就是左子树-右子树的值(或者右子树-左子树也是可以的)          ---每个结点都有平衡因子,平衡因子就是当前结点的左右子树相减的值(用绝对值来考虑比较方便)
//但是平衡因子也可能是-2 -1 0 1 2,都要理解

//2.一个 avl 树或者是空树,或者是具有以下性质的搜索二叉树:
//ps.1:它的左右子树都是 avl 树
//ps.2:左右子树高度之差(简称平衡因子)的绝对值不超过 1(-1/0/1)

//3.如果一个搜索二叉树是高度平衡的,他就是 avl 树,如果它有 n 个结点,其高度可保持在 O(log2 n),搜索时间复杂度 O(log2 n)





//4.二叉搜索树不一定是完全二叉树









//二丶  对于自己实现avl 树的测试
#include"11_AVL 树的实现.h"

void test_AVLTree()
{
    AVLTree<int,int> t1;
    int arr[]={4,2,6,1,3,5,15,7,16,14};//插入的这种降序的数字,就会形成单链,左子树单链那就要右单旋,一直插就会一直右单旋
    for(auto& e:arr)
    {
        t1.insert(make_pair(e,e));
    }

    t1.inorder();//通过遍历可以得知,现在旋转是有问题的

    cout<<t1.isbalance()<<endl;
}


//-----插入的升序就会形成做单旋,因为升序会形成单链的右子树
//----学会了右单旋就基本掌握了左单旋,但是最重要的是掌握双旋转

//int main(void)
//{
//    test_AVLTree();
//}




